#include "ArbolBSharpFrontCoding.h"

using namespace std;

const char ArbolBSharpFrontCoding::HIJO_IZQ = 0;
const char ArbolBSharpFrontCoding::HIJO_DER = 1;

const long ArbolBSharpFrontCoding::LONG_REGISTROS = 208;
const long ArbolBSharpFrontCoding::LONG_PUNTERO = 8;
const long ArbolBSharpFrontCoding::LONG_CLAVE = 200;

const short ArbolBSharpFrontCoding::NODO_RAIZ = 1;
const short ArbolBSharpFrontCoding::NODO_HOJA = 2;
const short ArbolBSharpFrontCoding::NODO_INDICE = 3;

const long ArbolBSharpFrontCoding::BLOQUE_CABECERA = 0;
const long ArbolBSharpFrontCoding::BLOQUE_RAIZ = 1;

const long ArbolBSharpFrontCoding::NUM_NODO_RAIZ = 1;

ArbolBSharpFrontCoding::ArbolBSharpFrontCoding() {
	this->raiz = NodoBSharpStringLong(NODO_RAIZ);
}

void ArbolBSharpFrontCoding::Crear(char* filePathName)
{
	this->fileName = filePathName;
	ManejadorAccesoDatos manejadorDatos = ManejadorAccesoDatos(filePathName, CREAR);

	this->cabecera.EspacioMaximoAOcupar = manejadorDatos.getTamanioBloques() - (2*sizeof(long)); //Datos de control
	this->cabecera.UltimoBloque = BLOQUE_RAIZ;
	this->cabecera.UltimoNodo = NUM_NODO_RAIZ;

	//Guardo los datos de control del arbol (cabecera del arbol)
	GuardarCabecera();

	this->raiz.numBloque = BLOQUE_RAIZ;
	this->raiz.numNodo = NUM_NODO_RAIZ;
	this->raiz.Salvar(filePathName);
}

void ArbolBSharpFrontCoding::Abrir(char* filePathName)
{
	this->fileName = filePathName;

	//Leo los datos de control del arbol
	RecuperarCabecera();

	ManejadorAccesoDatos manejadorDatos = ManejadorAccesoDatos(filePathName, ABRIR);

	char* bloque = manejadorDatos.leerBloque(BLOQUE_RAIZ);
	Puntero punteroRaiz;
	punteroRaiz.numBloque = BLOQUE_RAIZ;
	punteroRaiz.numNodo = NUM_NODO_RAIZ;

	this->raiz.Obtener(filePathName, punteroRaiz);

	free(bloque);
}

void ArbolBSharpFrontCoding::InsertarRegistro(RegistroBSharpStringLong registro)
{
	registro.clave = this->BalancearCadena(registro.clave);

	//Verifico si la raiz esta siendo usada como hoja o no
	if(this->raiz.punteros.empty())
	{
		//Verifico que no este llena
		if((this->raiz.CalcularTamanio(this->raiz) + 200) < this->cabecera.EspacioMaximoAOcupar)
		{
			this->AgregarClaveOrdenada(&(this->raiz), registro);
			this->raiz.cantRegistrosUsados++;
			this->raiz.Salvar(this->fileName);
		}
		else
		{
			//SINO SPLIT DE LA RAIZ QUE SE USABA DE HOJA!!
			//Agrego la clave igual y despues hago el split
			this->AgregarClaveOrdenada(&(this->raiz), registro);
			NodoBSharpStringLong hijoIzq = this->CrearHijo(this->raiz, HIJO_IZQ);

			Puntero puntIzq;
			puntIzq.numBloque = hijoIzq.numBloque;
			puntIzq.numNodo = hijoIzq.numNodo;

			this->cabecera.CantNodosHojas++;
			this->cabecera.UltimoNodo++;
			this->cabecera.UltimoBloque++;

			NodoBSharpStringLong hijoDer = this->CrearHijo(this->raiz, HIJO_DER);

			Puntero puntDer;
			puntDer.numBloque = hijoDer.numBloque;
			puntDer.numNodo = hijoDer.numNodo;

			hijoIzq.siguiente = puntDer;
			hijoDer.anterior = puntIzq;

			hijoIzq.Salvar(this->fileName);
			hijoDer.Salvar(this->fileName);

			this->cabecera.CantNodosHojas++;
			this->cabecera.UltimoNodo++;
			this->cabecera.UltimoBloque++;

			//Rearmo la raiz
			this->raiz.claves.clear();
			this->raiz.punteros.clear();
			this->raiz.registros.clear();
			this->raiz.cantClavesUsadas = 1;
			this->raiz.cantRegistrosUsados = 0;

			this->raiz.claves.push_back(hijoIzq.registros[hijoIzq.registros.size() - 1].clave);
			this->raiz.punteros.push_back(puntIzq);
			this->raiz.punteros.push_back(puntDer);

			this->raiz.Salvar(this->fileName);

			//Guardo los datos de control del arbol (cabecera del arbol)
			GuardarCabecera();
		}
	}
	else
	{
		//Se busca el nodo donde debe ir y se inserta
		vector<Puntero> camino;

		Puntero puntero;
		puntero.numBloque = this->raiz.numBloque;
		puntero.numNodo = this->raiz.numNodo;
		camino.push_back(puntero);

		Puntero punteroSiguiente = this->BuscarSiguiente(this->raiz, registro.clave);
		NodoBSharpStringLong nodo;
		nodo.Obtener(this->fileName, punteroSiguiente);

		while(nodo.tipo != NODO_HOJA)
		{
			Puntero puntAux;
			puntAux.numBloque = punteroSiguiente.numBloque;
			puntAux.numNodo = nodo.numNodo;
			camino.push_back(puntAux);
			punteroSiguiente = this->BuscarSiguiente(nodo, registro.clave);
			nodo.Limpiar();
			nodo.Obtener(this->fileName, punteroSiguiente);
		}

		if((nodo.CalcularTamanio(nodo) + registro.CalcularTamanio()) < this->cabecera.EspacioMaximoAOcupar)
		{
			//Agrego la clave y luego checkeo si hay que hacer split o no
			this->AgregarClaveOrdenada(&nodo, registro);
			nodo.cantRegistrosUsados++;
			nodo.Salvar(this->fileName);
		}
		else
		{
			//Debo verificar si el nodo es el primero o el ultimo ya que en esos casos no puedo
			//redistribuir con el anterior o el siguiente respectivamente porque dependen de nodos
			//indices diferentes
			NodoBSharpStringLong nodoPadre;
			nodoPadre.Obtener(this->fileName, camino.back());

			bool esPrimero = this->EsPrimerHijo(nodoPadre, nodo);
			bool esUltimo = this->EsUltimoHijo(nodoPadre, nodo);
			bool pudeRedistribuir = false;

			//Verifico primero si puedo hacer redistribucion con alguno de sus hermanos
			if(nodo.siguiente.numNodo != -1 && !esUltimo)
			{
				NodoBSharpStringLong nodoSiguiente;
				nodoSiguiente.Obtener(this->fileName, nodo.siguiente);

				if((nodoSiguiente.CalcularTamanio(nodoSiguiente) + registro.CalcularTamanio()) < this->cabecera.EspacioMaximoAOcupar)
				{
					//Agrego la clave
					this->AgregarClaveOrdenada(&nodo, registro);
					nodo.cantRegistrosUsados++;

					pudeRedistribuir = true;

					//Busco que registro muevo de un lado a otro
					RegistroBSharpStringLong registroAPasar = nodo.registros.back();

					nodo.registros.pop_back();
					nodo.cantRegistrosUsados--;

					string claveVieja = registroAPasar.clave;
					string claveNueva = nodo.registros.back().clave;

					//Pongo el registro en la primera posicion del nodo siguiente
					vector<RegistroBSharpStringLong>::iterator itSiguiente;
					itSiguiente = nodoSiguiente.registros.begin();
					nodoSiguiente.registros.insert(itSiguiente, registroAPasar);
					nodoSiguiente.cantRegistrosUsados++;

					nodo.Salvar(this->fileName);
					nodoSiguiente.Salvar(this->fileName);

					this->ReemplazarClave(claveVieja, claveNueva, camino.back());
				}
				else if(nodo.anterior.numNodo != -1 && !esPrimero)
				{
					NodoBSharpStringLong nodoAnterior;
					nodoAnterior.Obtener(this->fileName, nodo.anterior);

					if((nodoAnterior.CalcularTamanio(nodoAnterior) + registro.CalcularTamanio()) < this->cabecera.EspacioMaximoAOcupar)
					{
						//Agrego la clave
						this->AgregarClaveOrdenada(&nodo, registro);
						nodo.cantRegistrosUsados++;

						pudeRedistribuir = true;

						//Busco que registro muevo de un lado a otro
						RegistroBSharpStringLong registroAPasar = nodo.registros.front();

						nodo.registros.erase(nodo.registros.begin());
						nodo.cantRegistrosUsados--;

						string claveVieja = nodoAnterior.registros.back().clave;
						string claveNueva = registroAPasar.clave;;

						//Pongo el registro en la ultima posicion del nodo anterior
						nodoAnterior.registros.push_back(registroAPasar);
						nodoAnterior.cantRegistrosUsados++;

						nodo.Salvar(this->fileName);
						nodoAnterior.Salvar(this->fileName);

						this->ReemplazarClave(claveVieja, claveNueva, camino.back());
					}
				}
			}
			else if(nodo.anterior.numNodo != -1 && !esPrimero)
			{
				NodoBSharpStringLong nodoAnterior;
				nodoAnterior.Obtener(this->fileName, nodo.anterior);

				if((nodoAnterior.CalcularTamanio(nodoAnterior) + registro.CalcularTamanio()) < this->cabecera.EspacioMaximoAOcupar)
				{
					//Agrego la clave
					this->AgregarClaveOrdenada(&nodo, registro);
					nodo.cantRegistrosUsados++;

					pudeRedistribuir = true;

					//Busco que registro muevo de un lado a otro
					RegistroBSharpStringLong registroAPasar = nodo.registros.front();

					nodo.registros.erase(nodo.registros.begin());
					nodo.cantRegistrosUsados--;

					string claveVieja = nodoAnterior.registros.back().clave;
					string claveNueva = registroAPasar.clave;;

					//Pongo el registro en la ultima posicion del nodo anterior
					nodoAnterior.registros.push_back(registroAPasar);
					nodoAnterior.cantRegistrosUsados++;

					nodo.Salvar(this->fileName);
					nodoAnterior.Salvar(this->fileName);

					this->ReemplazarClave(claveVieja, claveNueva, camino.back());
				}
			}

			//Si no logre redistribuir porque sus hermanos estan llenos, hago SPLIT
			if(!pudeRedistribuir)
			{
				//	SPLIT!!
				//Intento juntarme siempre con mi hermano izquierdo a no ser que sea el primer hijo
				if(nodo.anterior.numNodo != -1 && !esPrimero)
				{
					NodoBSharpStringLong nodoIzq;
					nodoIzq.Obtener(this->fileName, nodo.anterior);

					string primerClaveAReemplazar = nodoIzq.registros.back().clave;

					//Agrego la clave
					this->AgregarClaveOrdenada(&nodo, registro);
					nodo.cantRegistrosUsados++;

					NodoBSharpStringLong nodoDer(NODO_HOJA);

					nodoDer.numBloque = this->cabecera.UltimoBloque + 1;
					nodoDer.numNodo = this->cabecera.UltimoNodo + 1;

					this->cabecera.UltimoNodo++;
					this->cabecera.UltimoBloque++;

					vector<RegistroBSharpStringLong> vectorAuxiliarDeRegistros;

					for(int i = 0; i < nodoIzq.registros.size(); i++)
					{
						vectorAuxiliarDeRegistros.push_back(nodoIzq.registros[i]);
					}
					nodoIzq.registros.clear();
					nodoIzq.cantRegistrosUsados = 0;

					for(int j = 0; j < nodo.registros.size(); j++)
					{
						vectorAuxiliarDeRegistros.push_back(nodo.registros[j]);
					}
					nodo.registros.clear();
					nodo.cantRegistrosUsados = 0;

					bool lleneIzquierdo = false;
					bool lleneCentro = false;

					//Armo los 3 nodos en los que se va a dividir
					for(int k = 0; k < vectorAuxiliarDeRegistros.size(); k++)
					{
						if(!lleneIzquierdo) {
							nodoIzq.registros.push_back(vectorAuxiliarDeRegistros[k]);
							nodoIzq.cantRegistrosUsados++;

							if(nodoIzq.CalcularTamanio(nodoIzq) + vectorAuxiliarDeRegistros[k].CalcularTamanio() > (this->cabecera.EspacioMaximoAOcupar * 2 / 3)) {
								lleneIzquierdo = true;
							}
						}
						else {
							if(!lleneCentro) {
								nodo.registros.push_back(vectorAuxiliarDeRegistros[k]);
								nodo.cantRegistrosUsados++;

								if(nodo.CalcularTamanio(nodo) + vectorAuxiliarDeRegistros[k].CalcularTamanio() > (this->cabecera.EspacioMaximoAOcupar * 2 / 3)) {
									lleneCentro = true;
								}
							}
							else {
								nodoDer.registros.push_back(vectorAuxiliarDeRegistros[k]);
								nodoDer.cantRegistrosUsados++;
							}
						}
					}

					string claveDeReemplazo = nodoIzq.registros.back().clave;

					this->ReemplazarClave(primerClaveAReemplazar, claveDeReemplazo, camino.back());

					//Pongo los punteros anteriores y siguientes como se deben. El hijo izquierdo queda igual
					nodoDer.siguiente.numBloque = nodo.siguiente.numBloque;
					nodoDer.siguiente.numNodo = nodo.siguiente.numNodo;

					nodo.siguiente.numBloque = nodoDer.numBloque;
					nodo.siguiente.numNodo = nodoDer.numNodo;

					nodoDer.anterior.numBloque = nodo.numBloque;
					nodoDer.anterior.numNodo = nodo.numNodo;

					//Al siguiente del ultimo le tengo que avisar que puse un nodo en el medio
					NodoBSharpStringLong nodoActualizable;
					nodoActualizable.Obtener(this->fileName, nodoDer.siguiente);

					nodoActualizable.anterior.numBloque = nodoDer.numBloque;
					nodoActualizable.anterior.numNodo = nodoDer.numNodo;

					nodoActualizable.Salvar(this->fileName);


					//Promover clave
					string claveAPromover = nodo.registros.back().clave;
					Puntero punteroHijoNuevo;
					punteroHijoNuevo.numBloque = nodoDer.numBloque;
					punteroHijoNuevo.numNodo = nodoDer.numNodo;

					nodoIzq.Salvar(this->fileName);
					nodo.Salvar(this->fileName);
					nodoDer.Salvar(this->fileName);

					this->Promover(camino, punteroHijoNuevo, claveAPromover);

					//Guardo los datos de control del arbol (cabecera del arbol)
					GuardarCabecera();
				}
				else
				{
					string primerClaveAReemplazar = nodo.registros.back().clave;

					//Agrego la clave
					this->AgregarClaveOrdenada(&nodo, registro);
					nodo.cantRegistrosUsados++;

					//Juntarme con mi hermano derecho
					NodoBSharpStringLong nodoDer;
					nodoDer.Obtener(this->fileName, nodo.siguiente);

					NodoBSharpStringLong nodoMasDer(NODO_HOJA);

					nodoMasDer.numBloque = this->cabecera.UltimoBloque + 1;
					nodoMasDer.numNodo = this->cabecera.UltimoNodo + 1;

					this->cabecera.UltimoNodo++;
					this->cabecera.UltimoBloque++;

					vector<RegistroBSharpStringLong> vectorAuxiliarDeRegistros;

					for(int i = 0; i < nodo.registros.size(); i++)
					{
						vectorAuxiliarDeRegistros.push_back(nodo.registros[i]);
					}
					nodo.registros.clear();
					nodo.cantRegistrosUsados = 0;

					for(int j = 0; j < nodoDer.registros.size(); j++)
					{
						vectorAuxiliarDeRegistros.push_back(nodoDer.registros[j]);
					}
					nodoDer.registros.clear();
					nodoDer.cantRegistrosUsados = 0;

					bool lleneNodo = false;
					bool lleneNodoDer = false;

					//Armo los 3 nodos en los que se va a dividir
					for(int k = 0; k < vectorAuxiliarDeRegistros.size(); k++)
					{
						if(!lleneNodo) {
							nodo.registros.push_back(vectorAuxiliarDeRegistros[k]);
							nodo.cantRegistrosUsados++;

							if(nodo.CalcularTamanio(nodo) + vectorAuxiliarDeRegistros[k].CalcularTamanio() > (this->cabecera.EspacioMaximoAOcupar * 2 / 3)) {
								lleneNodo = true;
							}
						}
						else {
							if(!lleneNodoDer) {
								nodoDer.registros.push_back(vectorAuxiliarDeRegistros[k]);
								nodoDer.cantRegistrosUsados++;

								if(nodoDer.CalcularTamanio(nodoDer) + vectorAuxiliarDeRegistros[k].CalcularTamanio() > (this->cabecera.EspacioMaximoAOcupar * 2 / 3)) {
									lleneNodoDer = true;
								}
							}
							else {
								nodoMasDer.registros.push_back(vectorAuxiliarDeRegistros[k]);
								nodoMasDer.cantRegistrosUsados++;
							}

						}
					}

					string claveDeReemplazo = nodo.registros.back().clave;

					this->ReemplazarClave(primerClaveAReemplazar, claveDeReemplazo, camino.back());

					//Pongo los punteros anteriores y siguientes como se deben. El hijo izquierdo queda igual
					nodoMasDer.siguiente.numBloque = nodoDer.siguiente.numBloque;
					nodoMasDer.siguiente.numNodo = nodoDer.siguiente.numNodo;

					nodoDer.siguiente.numBloque = nodoMasDer.numBloque;
					nodoDer.siguiente.numNodo = nodoMasDer.numNodo;

					nodoMasDer.anterior.numBloque = nodoDer.numBloque;
					nodoMasDer.anterior.numNodo = nodoDer.numNodo;

					//Promover clave
					string claveAPromover = nodoDer.registros.back().clave;
					Puntero punteroHijoNuevo;
					punteroHijoNuevo.numBloque = nodoMasDer.numBloque;
					punteroHijoNuevo.numNodo = nodoMasDer.numNodo;

					nodo.Salvar(this->fileName);
					nodoDer.Salvar(this->fileName);
					nodoMasDer.Salvar(this->fileName);

					//Al siguiente del ultimo le tengo que avisar que puse un nodo en el medio
					NodoBSharpStringLong nodoActualizable;
					nodoActualizable.Obtener(this->fileName, nodoMasDer.siguiente);

					nodoActualizable.anterior.numBloque = nodoMasDer.numBloque;
					nodoActualizable.anterior.numNodo = nodoMasDer.numNodo;

					nodoActualizable.Salvar(this->fileName);

					this->Promover(camino, punteroHijoNuevo, claveAPromover);

					//Guardo los datos de control del arbol (cabecera del arbol)
					GuardarCabecera();
				}
			}
		}
	}
}

//Verifica si el nodoHijo es el primer nodo apuntado por el padre. El nodo padre es siempre INDICE o RAIZ
bool ArbolBSharpFrontCoding::EsPrimerHijo(NodoBSharpStringLong nodoPadre, NodoBSharpStringLong nodoHijo)
{
	Puntero punteroAlHijo = nodoPadre.punteros.front();

	return (punteroAlHijo.numNodo == nodoHijo.numNodo);
}

//Verifica si el nodoHijo es el ultimo nodo apuntado por el padre. El nodo padre es siempre INDICE o RAIZ
bool ArbolBSharpFrontCoding::EsUltimoHijo(NodoBSharpStringLong nodoPadre, NodoBSharpStringLong nodoHijo)
{
	Puntero punteroAlHijo = nodoPadre.punteros.back();

	return (punteroAlHijo.numNodo == nodoHijo.numNodo);
}

//Reemplaza la clave vieja por la clave nueva en el nodo a donde apunta el puntero
void ArbolBSharpFrontCoding::ReemplazarClave(string claveVieja, string claveNueva, Puntero puntero)
{
	NodoBSharpStringLong nodo;
	nodo.Obtener(this->fileName, puntero);

	int i = 0;
	bool encontrado = false;

	while(i < nodo.claves.size() && !encontrado)
	{
		if(nodo.claves.at(i).compare(claveVieja) == 0)
			encontrado = true;
		else
			i++;
	}

	//Seguro siempre lo encuentra
	nodo.claves[i] = claveNueva;
	nodo.Salvar(this->fileName);

	//Si la raiz fue la ultima modificacion, entonces la cargo de vuelta
	if(nodo.tipo == NODO_RAIZ)
	{
		this->raiz.Limpiar();

		ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

		Puntero punteroRaiz;
		punteroRaiz.numBloque = BLOQUE_RAIZ;
		punteroRaiz.numNodo = NUM_NODO_RAIZ;

		this->raiz.Obtener(this->fileName, punteroRaiz);
	}
}

//Reemplaza la clave vieja por la clave nueva en el nodo a donde apunta el puntero
void ArbolBSharpFrontCoding::ReemplazarClaveGeneral(string claveVieja, string claveNueva)
{
	NodoBSharpStringLong nodo;
	Puntero puntero;

	puntero.numBloque = BLOQUE_RAIZ;
	puntero.numNodo = NUM_NODO_RAIZ;

	int i = 0;
	bool encontrado = false;
	bool encontradoInterno = false;

	nodo.Obtener(this->fileName, puntero);

	while(!encontrado && nodo.tipo != NODO_HOJA) {
		i = 0;
		encontradoInterno = false;

		while(i < nodo.claves.size() && !encontradoInterno)
		{
			if(nodo.claves.at(i).compare(claveVieja) < 0)
				i++;
			else
				encontradoInterno = true;
		}

		if(encontradoInterno) {
			if(nodo.claves.at(i).compare(claveVieja) == 0) {
				encontrado = true;
			} else {
				puntero = nodo.punteros[i];
				nodo.Limpiar();
				nodo.Obtener(this->fileName, puntero);
			}
		}
		else {
			puntero = nodo.punteros[i];
			nodo.Limpiar();
			nodo.Obtener(this->fileName, puntero);
		}
	}

	if(nodo.tipo != NODO_HOJA) {
		nodo.claves[i] = claveNueva;
		nodo.Salvar(this->fileName);

		if(nodo.tipo == NODO_RAIZ)
		{
			this->raiz.Limpiar();

			ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

			Puntero punteroRaiz;
			punteroRaiz.numBloque = BLOQUE_RAIZ;
			punteroRaiz.numNodo = NUM_NODO_RAIZ;

			this->raiz.Obtener(this->fileName, punteroRaiz);
		}
	}
}

bool ArbolBSharpFrontCoding::ModificarRegistro(string clave, long valor, long valorExtra)
{
	string claveCompleta = this->BalancearCadena(clave);
	bool encontrado = false;
	int pos = 0;

	if(this->raiz.cantRegistrosUsados > 0) //La raiz es hoja
	{
		//	Busco si esta en el nodo
		while(!encontrado && pos < this->raiz.cantRegistrosUsados)
		{
			if(claveCompleta.compare(this->raiz.registros[pos].clave) == 0)
				encontrado = true;
			else
				pos++;
		}

		//El registro con esa clave no existe
		if(!encontrado)
			return false;
		else
		{
			this->raiz.registros[pos].valor = valor;
			this->raiz.registros[pos].valorExtra = valorExtra;
			this->raiz.Salvar(this->fileName);
			return true;
		}
	}
	else
	{
		// Se busca el nodo donde debe ir y se modifica
		Puntero puntero = this->BuscarSiguiente(this->raiz, claveCompleta);
		NodoBSharpStringLong nodo;
		nodo.Obtener(this->fileName, puntero);

		while(nodo.tipo != NODO_HOJA)
		{
			puntero = this->BuscarSiguiente(nodo, claveCompleta);
			nodo.Limpiar();
			nodo.Obtener(this->fileName, puntero);
		}

		//Busco si esta en el nodo
		while(!encontrado && pos < nodo.cantRegistrosUsados)
		{
			if(claveCompleta.compare(nodo.registros[pos].clave) == 0)
				encontrado = true;
			else
				pos++;
		}

		//La clave no existe
		if(!encontrado)
			return false;
		else
		{
			nodo.registros[pos].valor = valor;
			nodo.registros[pos].valorExtra = valorExtra;
			nodo.Salvar(this->fileName);
			return true;
		}
	}
}

void ArbolBSharpFrontCoding::EliminarRegistro(string clave) {

	string claveCompleta = this->BalancearCadena(clave);
	//Se busca si existe la clave
	vector<Puntero> camino;

	Puntero puntero;
	puntero.numBloque = this->raiz.numBloque;
	puntero.numNodo = this->raiz.numNodo;
	camino.push_back(puntero);

	NodoBSharpStringLong nodo;

	//Si la raiz la uso como hoja
	if(this->raiz.cantRegistrosUsados > 0)
	{
		nodo = this->raiz;
	}
	else
	{
		Puntero punteroSiguiente = this->BuscarSiguiente(this->raiz, claveCompleta);
		nodo.Obtener(this->fileName, punteroSiguiente);

		while(nodo.tipo != NODO_HOJA)
		{
			Puntero puntAux;
			puntAux.numBloque = punteroSiguiente.numBloque;
			puntAux.numNodo = nodo.numNodo;
			camino.push_back(puntAux);
			punteroSiguiente = this->BuscarSiguiente(nodo, claveCompleta);
			nodo.Limpiar();
			nodo.Obtener(this->fileName, punteroSiguiente);
		}
	}

	//Me fijo si existe o no la clave
	int i = 0;
	bool termino = false;

	while(!termino && i < nodo.registros.size())
	{
		if(claveCompleta.compare(nodo.registros[i].clave) <= 0)
			termino = true;
		else
			i++;
	}

	//Si termino se puede haber encontrado o no
	if(termino)
	{
		//Si lo encontro lo elimino, sino devuelvo
		if(claveCompleta.compare(nodo.registros[i].clave) == 0)
		{
			if(nodo.tipo == NODO_RAIZ)
			{
				vector<RegistroBSharpStringLong>::iterator it;

				it = nodo.registros.begin();
				nodo.registros.erase(it + i);

				nodo.cantRegistrosUsados--;

				nodo.Salvar(this->fileName);

				//Recargo la raiz
				this->raiz.Limpiar();

				ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

				Puntero punteroRaiz;
				punteroRaiz.numBloque = BLOQUE_RAIZ;
				punteroRaiz.numNodo = NUM_NODO_RAIZ;

				this->raiz.Obtener(this->fileName, punteroRaiz);

			}
			else
			{
				RegistroBSharpStringLong registro = nodo.registros[i];

				NodoBSharpStringLong nodoPadre;
				nodoPadre.Obtener(this->fileName, camino.back());

				bool esPrimero = this->EsPrimerHijo(nodoPadre, nodo);
				bool esUltimo = this->EsUltimoHijo(nodoPadre, nodo);
				bool pudeRedistribuir = false;

				//Caso especial porque puedo tener solo 2 hijos
				if(nodoPadre.tipo == NODO_RAIZ && nodoPadre.cantClavesUsadas == 1)
				{
					if(nodo.CalcularTamanio(nodo) - registro.CalcularTamanio() < this->cabecera.EspacioMaximoAOcupar / 2)
					{
						if(nodo.siguiente.numNodo != -1)
						{
							NodoBSharpStringLong nodoSiguiente;
							nodoSiguiente.Obtener(this->fileName, nodo.siguiente);

							if((nodoSiguiente.CalcularTamanio(nodoSiguiente) - registro.CalcularTamanio()) > (this->cabecera.EspacioMaximoAOcupar / 2))
							{
								pudeRedistribuir = true;

								//Verifico si NO es el ultimo de los registros.
								if(i < nodo.cantRegistrosUsados - 1) {
									nodo.registros.erase(nodo.registros.begin() + i);

									nodo.cantRegistrosUsados--;

									RegistroBSharpStringLong registroUltimoAReemplazar = nodo.registros.back();
									RegistroBSharpStringLong registroARedistribuir = nodoSiguiente.registros.front();

									nodoSiguiente.registros.erase(nodoSiguiente.registros.begin());
									nodoSiguiente.cantRegistrosUsados--;

									this->AgregarClaveOrdenada(&(nodo), registroARedistribuir);
									nodo.cantRegistrosUsados++;

									nodo.Salvar(this->fileName);
									nodoSiguiente.Salvar(this->fileName);

									this->ReemplazarClaveGeneral(registroUltimoAReemplazar.clave, registroARedistribuir.clave);
								}
								else
								{
									nodo.registros.pop_back();
									nodo.cantRegistrosUsados--;

									RegistroBSharpStringLong registroARedistribuir = nodoSiguiente.registros.front();

									nodoSiguiente.registros.erase(nodoSiguiente.registros.begin());
									nodoSiguiente.cantRegistrosUsados--;

									this->AgregarClaveOrdenada(&(nodo), registroARedistribuir);
									nodo.cantRegistrosUsados++;

									nodo.Salvar(this->fileName);
									nodoSiguiente.Salvar(this->fileName);

									this->ReemplazarClaveGeneral(claveCompleta, registroARedistribuir.clave);
								}
							}
						}
						else
						{
							NodoBSharpStringLong nodoAnterior;
							nodoAnterior.Obtener(this->fileName, nodo.anterior);

							if((nodoAnterior.CalcularTamanio(nodoAnterior) - registro.CalcularTamanio()) > (this->cabecera.EspacioMaximoAOcupar / 2))
							{
								nodo.registros.erase(nodo.registros.begin() + i);

								nodo.cantRegistrosUsados--;

								RegistroBSharpStringLong registroARedistribuir = nodoAnterior.registros.back();

								nodoAnterior.registros.pop_back();
								nodoAnterior.cantRegistrosUsados--;

								RegistroBSharpStringLong registroDeReemplazo = nodoAnterior.registros.back();

								this->AgregarClaveOrdenada(&(nodo), registroARedistribuir);
								nodo.cantRegistrosUsados++;

								nodo.Salvar(this->fileName);
								nodoAnterior.Salvar(this->fileName);

								this->ReemplazarClaveGeneral(registroARedistribuir.clave, registroDeReemplazo.clave);
							}
						}

						if(!pudeRedistribuir)
						{
							//UNDERFLOWWWWWWWWWWW!!!!!!!!!!!
							nodoPadre.cantClavesUsadas = 0;
							nodoPadre.cantRegistrosUsados = 0;
							nodoPadre.punteros.clear();
							nodoPadre.claves.clear();
							nodoPadre.registros.clear();

							//Elimino el registro
							vector<RegistroBSharpStringLong>::iterator it;

							it = nodo.registros.begin();
							nodo.registros.erase(it + i);

							nodo.cantRegistrosUsados--;

							if(nodo.siguiente.numNodo != -1)
							{
								NodoBSharpStringLong nodoSiguiente;
								nodoSiguiente.Obtener(this->fileName, nodo.siguiente);

								for(int i = 0; i < nodo.cantRegistrosUsados; i++)
								{
									nodoPadre.registros.push_back(nodo.registros[i]);
									nodoPadre.cantRegistrosUsados++;
								}

								for(int j = 0; j < nodoSiguiente.cantRegistrosUsados; j++)
								{
									nodoPadre.registros.push_back(nodoSiguiente.registros[j]);
									nodoPadre.cantRegistrosUsados++;
								}
							}
							else
							{
								NodoBSharpStringLong nodoAnterior;
								nodoAnterior.Obtener(this->fileName, nodo.anterior);

								for(int i = 0; i < nodo.cantRegistrosUsados; i++)
								{
									nodoPadre.registros.push_back(nodoAnterior.registros[i]);
									nodoPadre.cantRegistrosUsados++;
								}

								for(int j = 0; j < nodo.cantRegistrosUsados; j++)
								{
									nodoPadre.registros.push_back(nodo.registros[j]);
									nodoPadre.cantRegistrosUsados++;
								}
							}

							nodoPadre.Salvar(this->fileName);

							//Recargo la raiz
							this->raiz.Limpiar();

							ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

							Puntero punteroRaiz;
							punteroRaiz.numBloque = BLOQUE_RAIZ;
							punteroRaiz.numNodo = NUM_NODO_RAIZ;

							this->raiz.Obtener(this->fileName, punteroRaiz);
						}
					}
					else
					{
						//Verifico si es el ultimo de los registros. Sino lo elimino y listo
						if(i < nodo.cantRegistrosUsados - 1) {
							vector<RegistroBSharpStringLong>::iterator it;

							it = nodo.registros.begin();
							nodo.registros.erase(it + i);

							nodo.cantRegistrosUsados--;

							nodo.Salvar(this->fileName);
						}
						else {
							nodo.registros.pop_back();

							nodo.cantRegistrosUsados--;

							nodo.Salvar(this->fileName);

							string claveNueva = nodo.registros.back().clave;

							if(nodo.siguiente.numBloque != -1) {
								this->ReemplazarClaveGeneral(claveCompleta, claveNueva);
							}
						}
					}
				}
				//Verifico si queda underflow al eliminar el registro
				else
				{
					if((nodo.CalcularTamanio(nodo) - registro.CalcularTamanio()) < (this->cabecera.EspacioMaximoAOcupar * 2 / 3))
					{
						//Veo si puedo redistribuir y luego si no puedo, es UNDERFLOW!!!!
						if(nodo.siguiente.numNodo != -1 && !esUltimo)
						{
							NodoBSharpStringLong nodoSiguiente;
							nodoSiguiente.Obtener(this->fileName, nodo.siguiente);

							if((nodoSiguiente.CalcularTamanio(nodoSiguiente) - registro.CalcularTamanio()) > (this->cabecera.EspacioMaximoAOcupar * 2 / 3))
							{
								pudeRedistribuir = true;

								//Verifico si NO es el ultimo de los registros.
								if(i < nodo.cantRegistrosUsados - 1) {
									nodo.registros.erase(nodo.registros.begin() + i);

									nodo.cantRegistrosUsados--;

									RegistroBSharpStringLong registroUltimoAReemplazar = nodo.registros.back();
									RegistroBSharpStringLong registroARedistribuir = nodoSiguiente.registros.front();

									nodoSiguiente.registros.erase(nodoSiguiente.registros.begin());
									nodoSiguiente.cantRegistrosUsados--;

									this->AgregarClaveOrdenada(&(nodo), registroARedistribuir);
									nodo.cantRegistrosUsados++;

									nodo.Salvar(this->fileName);
									nodoSiguiente.Salvar(this->fileName);

									this->ReemplazarClaveGeneral(registroUltimoAReemplazar.clave, registroARedistribuir.clave);
								}
								else {
									nodo.registros.pop_back();
									nodo.cantRegistrosUsados--;

									RegistroBSharpStringLong registroARedistribuir = nodoSiguiente.registros.front();

									nodoSiguiente.registros.erase(nodoSiguiente.registros.begin());
									nodoSiguiente.cantRegistrosUsados--;

									this->AgregarClaveOrdenada(&(nodo), registroARedistribuir);
									nodo.cantRegistrosUsados++;

									nodo.Salvar(this->fileName);
									nodoSiguiente.Salvar(this->fileName);

									this->ReemplazarClaveGeneral(claveCompleta, registroARedistribuir.clave);
								}
							}
							else if(nodo.anterior.numNodo != -1 && !esPrimero)
							{
								NodoBSharpStringLong nodoAnterior;
								nodoAnterior.Obtener(this->fileName, nodo.anterior);

								if((nodoAnterior.CalcularTamanio(nodoAnterior) - registro.CalcularTamanio()) > (this->cabecera.EspacioMaximoAOcupar * 2 / 3))
								{
									pudeRedistribuir = true;
									vector<RegistroBSharpStringLong>::iterator itAnterior;

									//Verifico si NO es el ultimo de los registros.
									if(i < nodo.cantRegistrosUsados - 1) {
										nodo.registros.erase(nodo.registros.begin() + i);

										nodo.cantRegistrosUsados--;

										RegistroBSharpStringLong registroARedistribuir = nodoAnterior.registros.back();

										nodoAnterior.registros.pop_back();
										nodoAnterior.cantRegistrosUsados--;

										RegistroBSharpStringLong registroDeReemplazo = nodoAnterior.registros.back();

										this->AgregarClaveOrdenada(&(nodo), registroARedistribuir);
										nodo.cantRegistrosUsados++;

										nodo.Salvar(this->fileName);
										nodoAnterior.Salvar(this->fileName);

										this->ReemplazarClaveGeneral(registroARedistribuir.clave, registroDeReemplazo.clave);
									}
									else {

										nodo.registros.pop_back();
										nodo.cantRegistrosUsados--;

										RegistroBSharpStringLong registroActualDeReemplazo = nodo.registros.back();

										RegistroBSharpStringLong registroARedistribuir = nodoAnterior.registros.back();

										nodoAnterior.registros.pop_back();
										nodoAnterior.cantRegistrosUsados--;

										RegistroBSharpStringLong registroDeReemplazo = nodoAnterior.registros.back();

										this->AgregarClaveOrdenada(&(nodo), registroARedistribuir);
										nodo.cantRegistrosUsados++;

										nodo.Salvar(this->fileName);
										nodoAnterior.Salvar(this->fileName);

										this->ReemplazarClaveGeneral(claveCompleta, registroActualDeReemplazo.clave);
										this->ReemplazarClaveGeneral(registroARedistribuir.clave, registroDeReemplazo.clave);
									}
								}
							}
						}
						else if(nodo.anterior.numNodo != -1 && !esPrimero)
						{
							NodoBSharpStringLong nodoAnterior;
							nodoAnterior.Obtener(this->fileName, nodo.anterior);

							if((nodoAnterior.CalcularTamanio(nodoAnterior) - registro.CalcularTamanio()) > (this->cabecera.EspacioMaximoAOcupar * 2 / 3))
							{
								pudeRedistribuir = true;

								//Verifico si NO es el ultimo de los registros.
								if(i < nodo.cantRegistrosUsados - 1) {
									nodo.registros.erase(nodo.registros.begin() + i);

									nodo.cantRegistrosUsados--;

									RegistroBSharpStringLong registroARedistribuir = nodoAnterior.registros.back();

									nodoAnterior.registros.pop_back();
									nodoAnterior.cantRegistrosUsados--;

									RegistroBSharpStringLong registroDeReemplazo = nodoAnterior.registros.back();

									this->AgregarClaveOrdenada(&(nodo), registroARedistribuir);
									nodo.cantRegistrosUsados++;

									nodo.Salvar(this->fileName);
									nodoAnterior.Salvar(this->fileName);

									this->ReemplazarClaveGeneral(registroARedistribuir.clave, registroDeReemplazo.clave);
								}
								else {

									nodo.registros.pop_back();
									nodo.cantRegistrosUsados--;

									RegistroBSharpStringLong registroActualDeReemplazo = nodo.registros.back();

									RegistroBSharpStringLong registroARedistribuir = nodoAnterior.registros.back();

									nodoAnterior.registros.pop_back();
									nodoAnterior.cantRegistrosUsados--;

									RegistroBSharpStringLong registroDeReemplazo = nodoAnterior.registros.back();

									this->AgregarClaveOrdenada(&(nodo), registroARedistribuir);
									nodo.cantRegistrosUsados++;

									nodo.Salvar(this->fileName);
									nodoAnterior.Salvar(this->fileName);

									this->ReemplazarClaveGeneral(claveCompleta, registroActualDeReemplazo.clave);
									this->ReemplazarClaveGeneral(registroARedistribuir.clave, registroDeReemplazo.clave);
								}
							}
						}

						if(!pudeRedistribuir) {
							//UNDERFLOWWWWWWWWWWW!!!!!!!!!!!

							if(nodo.siguiente.numNodo == -1 || esUltimo)
							{
								NodoBSharpStringLong nodoAnterior;
								NodoBSharpStringLong nodoMasAnterior;
								nodoAnterior.Obtener(this->fileName, nodo.anterior);
								nodoMasAnterior.Obtener(this->fileName, nodoAnterior.anterior);

								long tamanioTotal = nodo.CalcularTamanio(nodo) - registro.CalcularTamanio();
								tamanioTotal += nodoAnterior.CalcularTamanio(nodoAnterior);
								tamanioTotal += nodoMasAnterior.CalcularTamanio(nodoMasAnterior);

								if(tamanioTotal > (2 * this->cabecera.EspacioMaximoAOcupar))
								{
									vector<RegistroBSharpStringLong>::iterator it;

									it = nodo.registros.begin();
									nodo.registros.erase(it + i);

									nodo.cantRegistrosUsados--;

									//Debo redistribuir desde el hermano mas anterior
									nodoAnterior.registros.insert(nodoAnterior.registros.begin(), nodoMasAnterior.registros.back() );
									nodoMasAnterior.registros.pop_back();
									nodoMasAnterior.cantRegistrosUsados--;
									nodoAnterior.cantRegistrosUsados++;

									nodo.registros.insert(nodo.registros.begin(), nodoAnterior.registros.back() );
									nodoAnterior.registros.pop_back();
									nodoAnterior.cantRegistrosUsados--;
									nodo.cantRegistrosUsados++;

									string claveVieja1 = nodoAnterior.registros.front().clave;
									string claveVieja2 = nodo.registros.front().clave;
									string claveNueva1 = nodoMasAnterior.registros.back().clave;
									string claveNueva2 = nodoAnterior.registros.back().clave;

									this->ReemplazarClaveGeneral(claveVieja1, claveNueva1);
									this->ReemplazarClaveGeneral(claveVieja2, claveNueva2);

									nodoMasAnterior.Salvar(this->fileName);
									nodoAnterior.Salvar(this->fileName);
									nodo.Salvar(this->fileName);
								}
								else
								{
									RegistroBSharpStringLong registroNodo = nodo.registros.back();
									RegistroBSharpStringLong registroAnterior = nodoAnterior.registros.back();
									RegistroBSharpStringLong registroMasAnterior = nodoMasAnterior.registros.back();

									//Elimino el registro
									vector<RegistroBSharpStringLong>::iterator it;

									it = nodo.registros.begin();
									nodo.registros.erase(it + i);

									nodo.cantRegistrosUsados--;

									vector<RegistroBSharpStringLong> vectorAuxiliarDeRegistros;

									for(int j = 0; j < nodoAnterior.registros.size(); j++)
									{
										vectorAuxiliarDeRegistros.push_back(nodoAnterior.registros[j]);
									}
									nodoAnterior.registros.clear();
									nodoAnterior.cantRegistrosUsados = 0;

									for(int k = 0; k < nodo.registros.size(); k++)
									{
										vectorAuxiliarDeRegistros.push_back(nodo.registros[k]);
									}

									while(nodoMasAnterior.CalcularTamanio(nodoMasAnterior) + vectorAuxiliarDeRegistros.front().CalcularTamanio() < this->cabecera.EspacioMaximoAOcupar )
									{
										nodoMasAnterior.registros.push_back(vectorAuxiliarDeRegistros.front());
										vectorAuxiliarDeRegistros.erase(vectorAuxiliarDeRegistros.begin());
										nodoMasAnterior.cantRegistrosUsados++;
									}

									while(vectorAuxiliarDeRegistros.size() > 0)
									{
										nodoAnterior.registros.push_back(vectorAuxiliarDeRegistros.front());
										vectorAuxiliarDeRegistros.erase(vectorAuxiliarDeRegistros.begin());
										nodoAnterior.cantRegistrosUsados++;
									}

									RegistroBSharpStringLong registroMasAlto = nodoAnterior.registros.back();
									RegistroBSharpStringLong registroReemplazantePadre = nodoMasAnterior.registros.back();

									this->ReemplazarClaveGeneral(registroNodo.clave, registroMasAlto.clave);
									this->ReemplazarClaveGeneral(registroMasAnterior.clave, registroReemplazantePadre.clave);

									nodoAnterior.siguiente = nodo.siguiente;

									if(nodo.siguiente.numBloque != -1)
									{
										NodoBSharpStringLong nodoACambiarAnterior;
										nodoACambiarAnterior.Obtener(this->fileName, nodo.siguiente);

										nodoACambiarAnterior.anterior = nodoMasAnterior.siguiente;

										nodoACambiarAnterior.Salvar(this->fileName);
									}

									nodoMasAnterior.Salvar(this->fileName);
									nodoAnterior.Salvar(this->fileName);

									this->Despromover(registroAnterior.clave, camino);
								}
							}
							else if(nodo.anterior.numNodo == -1 || esPrimero)
							{

								NodoBSharpStringLong nodoSiguiente;
								NodoBSharpStringLong nodoMasSiguiente;
								nodoSiguiente.Obtener(this->fileName, nodo.siguiente);
								nodoMasSiguiente.Obtener(this->fileName, nodoSiguiente.siguiente);

								long tamanioTotal = nodo.CalcularTamanio(nodo) - registro.CalcularTamanio();
								tamanioTotal += nodoSiguiente.CalcularTamanio(nodoSiguiente);
								tamanioTotal += nodoMasSiguiente.CalcularTamanio(nodoMasSiguiente);

								if(tamanioTotal > (2 * this->cabecera.EspacioMaximoAOcupar))
								{
									vector<RegistroBSharpStringLong>::iterator it;

									it = nodo.registros.begin();
									nodo.registros.erase(it + i);

									nodo.cantRegistrosUsados--;

									string claveVieja1 = nodoSiguiente.registros.back().clave;
									string claveVieja2 = nodo.registros.back().clave;
									string claveNueva1 = nodoMasSiguiente.registros.front().clave;
									string claveNueva2 = nodoSiguiente.registros.front().clave;

									//Debo redistribuir desde el hermano mas siguiente
									nodoSiguiente.registros.push_back(nodoMasSiguiente.registros.front());
									nodoMasSiguiente.registros.erase(nodoMasSiguiente.registros.begin());
									nodoMasSiguiente.cantRegistrosUsados--;
									nodoSiguiente.cantRegistrosUsados++;

									nodo.registros.push_back(nodoSiguiente.registros.front());
									nodoSiguiente.registros.erase(nodoSiguiente.registros.begin());
									nodoSiguiente.cantRegistrosUsados--;
									nodo.cantRegistrosUsados++;

									this->ReemplazarClaveGeneral(claveVieja1, claveNueva1);
									this->ReemplazarClaveGeneral(claveVieja2, claveNueva2);

									nodoMasSiguiente.Salvar(this->fileName);
									nodoSiguiente.Salvar(this->fileName);
									nodo.Salvar(this->fileName);
								}
								else
								{
									RegistroBSharpStringLong registroNodo = nodo.registros.back();
									RegistroBSharpStringLong registroSiguiente = nodoSiguiente.registros.back();
									RegistroBSharpStringLong registroMasSiguiente = nodoMasSiguiente.registros.back();

									//Elimino el registro
									vector<RegistroBSharpStringLong>::iterator it;

									it = nodo.registros.begin();
									nodo.registros.erase(it + i);

									nodo.cantRegistrosUsados--;

									vector<RegistroBSharpStringLong> vectorAuxiliarDeRegistros;

									for(int i = 0; i < nodo.registros.size(); i++)
									{
										vectorAuxiliarDeRegistros.push_back(nodo.registros[i]);
									}
									nodo.registros.clear();
									nodo.cantRegistrosUsados = 0;

									for(int j = 0; j < nodoSiguiente.registros.size(); j++)
									{
										vectorAuxiliarDeRegistros.push_back(nodoSiguiente.registros[j]);
									}
									nodoSiguiente.registros.clear();
									nodoSiguiente.cantRegistrosUsados = 0;

									for(int k = 0; k < nodoMasSiguiente.registros.size(); k++)
									{
										vectorAuxiliarDeRegistros.push_back(nodoMasSiguiente.registros[k]);
									}

									while(nodo.CalcularTamanio(nodo) + vectorAuxiliarDeRegistros.front().CalcularTamanio() < this->cabecera.EspacioMaximoAOcupar )
									{
										nodo.registros.push_back(vectorAuxiliarDeRegistros.front());
										vectorAuxiliarDeRegistros.erase(vectorAuxiliarDeRegistros.begin());
										nodo.cantRegistrosUsados++;
									}

									while(vectorAuxiliarDeRegistros.size() > 0)
									{
										nodoSiguiente.registros.push_back(vectorAuxiliarDeRegistros.front());
										vectorAuxiliarDeRegistros.erase(vectorAuxiliarDeRegistros.begin());
										nodoSiguiente.cantRegistrosUsados++;
									}

									RegistroBSharpStringLong registroMasAlto = nodoSiguiente.registros.back();
									RegistroBSharpStringLong registroReemplazantePadre = nodo.registros.back();

									this->ReemplazarClaveGeneral(registroNodo.clave, registroReemplazantePadre.clave);

									//Si es el ultimo, reemplazo en un nivel mas arriba
									if(nodoMasSiguiente.siguiente.numBloque == -1)
									{
										this->ReemplazarClaveGeneral(registroMasSiguiente.clave, registroMasAlto.clave);
									}

									nodoSiguiente.siguiente = nodoMasSiguiente.siguiente;

									if(nodoMasSiguiente.siguiente.numBloque != -1)
									{
										NodoBSharpStringLong nodoACambiarAnterior;
										nodoACambiarAnterior.Obtener(this->fileName, nodoMasSiguiente.siguiente);

										nodoACambiarAnterior.anterior = nodo.siguiente;

										nodoACambiarAnterior.Salvar(this->fileName);
									}

									nodo.Salvar(this->fileName);
									nodoSiguiente.Salvar(this->fileName);

									this->Despromover(registroSiguiente.clave, camino);
								}
							}
							else
							{
								NodoBSharpStringLong nodoAnterior;
								NodoBSharpStringLong nodoSiguiente;
								nodoAnterior.Obtener(this->fileName, nodo.anterior);
								nodoSiguiente.Obtener(this->fileName, nodo.siguiente);

								RegistroBSharpStringLong registroNodo = nodo.registros.back();
								RegistroBSharpStringLong registroAnterior = nodoAnterior.registros.back();
								RegistroBSharpStringLong registroSiguiente = nodoSiguiente.registros.back();

								//Elimino el registro
								vector<RegistroBSharpStringLong>::iterator it;

								it = nodo.registros.begin();
								nodo.registros.erase(it + i);

								nodo.cantRegistrosUsados--;

								vector<RegistroBSharpStringLong> vectorAuxiliarDeRegistros;

								for(int j = 0; j < nodo.registros.size(); j++)
								{
									vectorAuxiliarDeRegistros.push_back(nodo.registros[j]);
								}
								nodo.registros.clear();
								nodo.cantRegistrosUsados = 0;

								for(int k = 0; k < nodoSiguiente.registros.size(); k++)
								{
									vectorAuxiliarDeRegistros.push_back(nodoSiguiente.registros[k]);
								}

								while(nodoAnterior.CalcularTamanio(nodoAnterior) + vectorAuxiliarDeRegistros.front().CalcularTamanio() < this->cabecera.EspacioMaximoAOcupar)
								{
									nodoAnterior.registros.push_back(vectorAuxiliarDeRegistros.front());
									vectorAuxiliarDeRegistros.erase(vectorAuxiliarDeRegistros.begin());
									nodoAnterior.cantRegistrosUsados++;
								}

								while(vectorAuxiliarDeRegistros.size() > 0)
								{
									nodo.registros.push_back(vectorAuxiliarDeRegistros.front());
									vectorAuxiliarDeRegistros.erase(vectorAuxiliarDeRegistros.begin());
									nodo.cantRegistrosUsados++;
								}

								RegistroBSharpStringLong registroReemplazanteMasAlto = nodo.registros.back();
								RegistroBSharpStringLong registroReemplazantePadre = nodoAnterior.registros.back();

								this->ReemplazarClaveGeneral(registroAnterior.clave, registroReemplazantePadre.clave);

								//Si es el ultimo, reemplazo en un nivel mas arriba
								if(nodoSiguiente.siguiente.numBloque == -1)
								{
									this->ReemplazarClaveGeneral(registroSiguiente.clave, registroReemplazanteMasAlto.clave);
								}

								nodo.siguiente = nodoSiguiente.siguiente;

								if(nodoSiguiente.siguiente.numBloque != -1)
								{
									NodoBSharpStringLong nodoACambiarAnterior;
									nodoACambiarAnterior.Obtener(this->fileName, nodoSiguiente.siguiente);

									nodoACambiarAnterior.anterior = nodoAnterior.siguiente;

									nodoACambiarAnterior.Salvar(this->fileName);
								}

								nodoAnterior.Salvar(this->fileName);
								nodo.Salvar(this->fileName);

								this->Despromover(registroNodo.clave, camino);
							}
						}
					}
					else {
						//Verifico si es el ultimo de los registros. Sino lo elimino y listo
						if(i < nodo.cantRegistrosUsados - 1) {
							vector<RegistroBSharpStringLong>::iterator it;

							it = nodo.registros.begin();
							nodo.registros.erase(it + i);

							nodo.cantRegistrosUsados--;

							nodo.Salvar(this->fileName);
						}
						else {
							nodo.registros.pop_back();

							nodo.cantRegistrosUsados--;

							nodo.Salvar(this->fileName);

							string claveNueva = nodo.registros.back().clave;

							if(nodo.siguiente.numBloque != -1) {
								this->ReemplazarClaveGeneral(claveCompleta, claveNueva);
							}
						}
					}
				}
			}
		}

	}
}

RegistroBSharpStringLong ArbolBSharpFrontCoding::ObtenerRegistro(string clave)
{
	RegistroBSharpStringLong registroNulo;
	string claveCompleta = this->BalancearCadena(clave);

	//Si la raiz no tiene punteros es porque se usa como hoja tambien y la busco ahi directo
	if(this->raiz.punteros.size() == 0)
	{
		//Busco la posicion del registro
		for(int i = 0; i < this->raiz.cantRegistrosUsados; i++)
		{
			if(this->raiz.registros[i].clave.compare(claveCompleta) == 0)
			{
				RegistroBSharpStringLong registroADevolver;
				registroADevolver.clave = this->raiz.registros[i].clave.substr(0, this->raiz.registros[i].clave.find_first_of("*"));
				registroADevolver.valor = this->raiz.registros[i].valor;
				registroADevolver.valorExtra = this->raiz.registros[i].valorExtra;
				return registroADevolver;
			}
		}
	}
	else
	{
		//La raiz no es hoja
		Puntero proximo;
		RegistroBSharpStringLong registro;
		NodoBSharpStringLong nodo;

		bool encontrado = BuscarInterno(this->raiz, claveCompleta, &proximo, &registro);
		bool busquedaExitosa = false;

		if(encontrado)
		{
			RegistroBSharpStringLong registroADevolver;
			registroADevolver.clave = registro.clave.substr(0, registro.clave.find_first_of("*"));
			registroADevolver.valor = registro.valor;
			registroADevolver.valorExtra = registro.valorExtra;
			return registroADevolver;
		}
		else
		{
			nodo.Obtener(this->fileName, proximo);

			while (!encontrado)
			{
				busquedaExitosa = BuscarInterno(nodo, claveCompleta, &proximo, &registro);

				if(busquedaExitosa)
				{
					RegistroBSharpStringLong registroADevolver;
					registroADevolver.clave = registro.clave.substr(0, registro.clave.find_first_of("*"));
					registroADevolver.valor = registro.valor;
					registroADevolver.valorExtra = registro.valorExtra;
					return registroADevolver;
				}
				else
				{
					if(proximo.numBloque == -1 && proximo.numNodo == -1)
						return registroNulo;
					else
					{
						nodo.Limpiar();
						nodo.Obtener(this->fileName, proximo);
					}
				}
			}
		}
	}
	return registroNulo;
}

string ArbolBSharpFrontCoding::BalancearCadena(string cadena)
{
	string stringAux;

	if(cadena.length() < LONG_CLAVE)
	{
		stringAux.append(cadena);

		for(int i = cadena.length(); i < LONG_CLAVE; i++)
			stringAux.append("*");
	}
	else
	{
		stringAux.append(cadena.substr(0, LONG_CLAVE));
	}

	return stringAux;

}

//Agrega la clave en el array ordenada y tambien el registro. Hay lugar seguro
void ArbolBSharpFrontCoding::AgregarClaveOrdenada(NodoBSharpStringLong* nodo, RegistroBSharpStringLong registro)
{
	if(nodo->registros.empty())
	{
		nodo->registros.push_back(registro);
	}
	else
	{
		//Busco la posicion
		int pos = 0;
		while( (pos < nodo->registros.size()) && (nodo->registros[pos].clave.compare(registro.clave)) < 0 )
			pos++;

		//Si hay que agregarla al final
		if(pos >= nodo->registros.size())
		{
			nodo->registros.push_back(registro);
		}
		else
		{
			vector<RegistroBSharpStringLong>::iterator it;
			it = nodo->registros.begin();
			nodo->registros.insert(it + pos, registro);
		}
	}
}

NodoBSharpStringLong ArbolBSharpFrontCoding::CrearHijo(NodoBSharpStringLong padre, char lado)
{
	NodoBSharpStringLong nodo(NODO_HOJA);
	long tamanioNodoPadre = (padre.CalcularTamanio(padre) / 2);
	long tamanioNodo = nodo.CalcularTamanio(nodo);

	nodo.numBloque = this->cabecera.UltimoBloque + 1;
	nodo.numNodo = this->cabecera.UltimoNodo + 1;
	int j = 0;

	if(lado == HIJO_IZQ)
	{
		while((tamanioNodo + padre.registros[j].CalcularTamanio()) < tamanioNodoPadre)
		{
			this->AgregarClaveOrdenada(&nodo, padre.registros[j]);
			nodo.cantRegistrosUsados++;
			j++;
			tamanioNodo += padre.registros[j].CalcularTamanio();
		}
	}
	else
	{
		while((tamanioNodo + padre.registros[j].CalcularTamanio()) < tamanioNodoPadre)
		{
			j++;
			tamanioNodo += padre.registros[j].CalcularTamanio();
		}

		for(int i = j; i < padre.registros.size(); i++)
		{
			this->AgregarClaveOrdenada(&nodo, padre.registros[i]);
			nodo.cantRegistrosUsados++;
		}
	}

	return nodo;
}

//Busca dentro del nodo el registro, si lo encuentra lo devuelve. Sino devuelve si puede el puntero al proximo
bool ArbolBSharpFrontCoding::BuscarInterno(NodoBSharpStringLong nodo, string clave, Puntero* puntero, RegistroBSharpStringLong* registro)
{
	int i = 0;
	bool termino = false;

	if(nodo.tipo == NODO_HOJA || (nodo.tipo == NODO_RAIZ && nodo.cantRegistrosUsados > 0))
	{
		while(!termino && i < nodo.registros.size())
		{
			if(clave.compare(nodo.registros[i].clave) <= 0)
				termino = true;
			else
				i++;
		}
	}
	else
	{
		while(!termino && i < nodo.claves.size())
		{
			if(clave <= nodo.claves[i])
				termino = true;
			else
				i++;
		}
	}


	if(termino)
	{//Encontro a donde apuntar o el exacto
		//Si es hoja: o lo encontro o no existe en el arbol
		if(nodo.tipo == NODO_HOJA)
		{
			//Si lo encontro
			if(clave.compare(nodo.registros[i].clave) == 0)
			{
				registro->clave = nodo.registros[i].clave;
				registro->valor = nodo.registros[i].valor;
				registro->valorExtra = nodo.registros[i].valorExtra;

				//Pseudo-asigno el puntero a null
				puntero->numBloque = -1;
				puntero->numNodo = -1;
				return true;
			}
			else
			{
				//Pseudo-asigno el puntero a null
				puntero->numBloque = -1;
				puntero->numNodo = -1;
				//Pseudo-asigno el registro a null
				registro->clave = -1;
				registro->valor = -1;
				registro->valorExtra = -1;
				return false;
			}
		}
		else
		{
			puntero->numBloque = nodo.punteros[i].numBloque;
			puntero->numNodo = nodo.punteros[i].numNodo;

			//Pseudo-asigno el registro a null
			registro->clave = -1;
			registro->valor = -1;
			registro->valorExtra = -1;
			return false;
		}
	}
	else //Salio del while porque llego al final
	{
		if(nodo.tipo == NODO_HOJA)
		{
			//Pseudo-asigno el puntero a null
			puntero->numBloque = -1;
			puntero->numNodo = -1;
			//Pseudo-asigno el registro a null
			registro->clave = -1;
			registro->valor = -1;
			registro->valorExtra = -1;
			return false;
		}
		else
		{
			puntero->numBloque = nodo.punteros[i].numBloque;
			puntero->numNodo = nodo.punteros[i].numNodo;

			//puntero = &nodo.punteros[i];
			//Pseudo-asigno el registro a null
			registro->clave = -1;
			registro->valor = -1;
			registro->valorExtra = -1;
			return false;
		}
	}
}

//Devuelve el offset al siguiente nodo. Solo recibe nodos NO de tipo Hoja
Puntero ArbolBSharpFrontCoding::BuscarSiguiente(NodoBSharpStringLong nodo, string clave)
{
	int i = 0;
	bool termino = false;

	while(!termino && i < nodo.claves.size())
	{
		if(clave.compare(nodo.claves[i]) <= 0)
			termino = true;
		else
			i++;
	}

	//Encontro a donde apuntar
	return nodo.punteros.at(i);
}

void ArbolBSharpFrontCoding::Despromover(string claveAEliminar, vector<Puntero> camino)
{
	//Busco la posicion a eliminar del nodoPadre
	int pos = 0;

	NodoBSharpStringLong nodoPadre;

	nodoPadre.Obtener(this->fileName, camino.back());
	camino.erase(camino.end());

	while( (pos < nodoPadre.claves.size()) && (nodoPadre.claves.at(pos).compare(claveAEliminar) < 0) )
		pos++;

	//Elimino la clave
	vector<string>::iterator itClaves;
	vector<Puntero>::iterator itPuntero;

	itClaves = nodoPadre.claves.begin();
	nodoPadre.claves.erase(itClaves + pos);
	nodoPadre.cantClavesUsadas--;

	itPuntero = nodoPadre.punteros.begin();
	nodoPadre.punteros.erase(itPuntero + 1 + pos);

	if(nodoPadre.tipo == NODO_RAIZ)
	{
		nodoPadre.Salvar(this->fileName);

		//Recargo la raiz
		this->raiz.Limpiar();

		ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

		Puntero punteroRaiz;
		punteroRaiz.numBloque = BLOQUE_RAIZ;
		punteroRaiz.numNodo = NUM_NODO_RAIZ;

		this->raiz.Obtener(this->fileName, punteroRaiz);

		return;
	}

	//Lo encuentra siempre. Verifico si NO queda con UNDERFLOW o no
	if(nodoPadre.CalcularTamanio(nodoPadre) > (this->cabecera.EspacioMaximoAOcupar / 2))
	{
		nodoPadre.Salvar(this->fileName);
	}
	else
	{
		//Intento redistribuir con alguno de sus hermanos
		NodoBSharpStringLong nodoAbuelo;
		nodoAbuelo.Obtener(this->fileName, camino.back());

		bool encontrado = false;
		int i = 0;

		//Busco en el abuelo donde lo apunta para conocer sus hermanos. LO ENCUENTRA SIEMPRE
		while(!encontrado)
		{
			if(nodoAbuelo.punteros[i].numBloque == nodoPadre.numBloque)
				encontrado = true;
			else
				i++;
		}

		bool pudeRedistribuir = false;

		//Si es el mas a la izquierda de los hijos
		if(i == 0)
		{
			NodoBSharpStringLong nodoHermanoDerecho;
			nodoHermanoDerecho.Obtener(this->fileName, nodoAbuelo.punteros[i+1]);

			if(nodoHermanoDerecho.CalcularTamanio(nodoHermanoDerecho) - 8 - nodoHermanoDerecho.claves.front().length() > (this->cabecera.EspacioMaximoAOcupar / 2))
			{
				pudeRedistribuir = true;

				//Busco la clave del abuelo que es mayor a la ultima del nodo padre
				//Lo encuentra seguro
				int i = 0;
				bool termino = false;
				while(!termino && i < nodoAbuelo.claves.size())
				{
					if(nodoAbuelo.claves[i].compare(nodoPadre.claves.back()) < 0)
						i++;
					else
						termino = true;
				}

				string claveParaElPadre;
				claveParaElPadre.assign(nodoAbuelo.claves[i]);

				nodoPadre.claves.push_back(claveParaElPadre);
				nodoPadre.punteros.push_back(nodoHermanoDerecho.punteros.front());
				nodoPadre.cantClavesUsadas++;

				nodoAbuelo.claves[i] = nodoHermanoDerecho.claves.front();

				nodoHermanoDerecho.claves.erase(nodoHermanoDerecho.claves.begin());
				nodoHermanoDerecho.punteros.erase(nodoHermanoDerecho.punteros.begin());
				nodoHermanoDerecho.cantClavesUsadas--;

				nodoPadre.Salvar(this->fileName);
				nodoHermanoDerecho.Salvar(this->fileName);
				nodoAbuelo.Salvar(this->fileName);

				if(nodoAbuelo.tipo == NODO_RAIZ)
				{
					//Recargo la raiz
					this->raiz.Limpiar();

					ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

					Puntero punteroRaiz;
					punteroRaiz.numBloque = BLOQUE_RAIZ;
					punteroRaiz.numNodo = NUM_NODO_RAIZ;

					this->raiz.Obtener(this->fileName, punteroRaiz);
				}
			}
		}
		//Si es el mas a la derecha de los hijos
		else if (i == nodoAbuelo.punteros.size() - 1)
		{
			NodoBSharpStringLong nodoHermanoIzquierdo;
			nodoHermanoIzquierdo.Obtener(this->fileName, nodoAbuelo.punteros[i-1]);

			if(nodoHermanoIzquierdo.CalcularTamanio(nodoHermanoIzquierdo) - 8 - nodoHermanoIzquierdo.claves.back().length() > (this->cabecera.EspacioMaximoAOcupar / 2))
			{
				pudeRedistribuir = true;

				//Busco la clave del abuelo que es mayor a la ultima del nodo padre
				//Lo encuentra seguro
				int i = nodoAbuelo.claves.size() - 1;
				bool termino = false;
				while(!termino && i >= 0)
				{
					if(nodoAbuelo.claves[i].compare(nodoPadre.claves.front()) > 0)
						i--;
					else
						termino = true;
				}

				string claveParaElPadre;
				claveParaElPadre.assign(nodoAbuelo.claves[i]);

				nodoPadre.claves.insert(nodoPadre.claves.begin(), claveParaElPadre);
				nodoPadre.punteros.insert(nodoPadre.punteros.begin(), nodoHermanoIzquierdo.punteros.back());
				nodoPadre.cantClavesUsadas++;

				nodoAbuelo.claves[i] = nodoHermanoIzquierdo.claves.back();

				nodoHermanoIzquierdo.claves.erase(nodoHermanoIzquierdo.claves.end());
				nodoHermanoIzquierdo.punteros.erase(nodoHermanoIzquierdo.punteros.end());
				nodoHermanoIzquierdo.cantClavesUsadas--;

				nodoPadre.Salvar(this->fileName);
				nodoHermanoIzquierdo.Salvar(this->fileName);
				nodoAbuelo.Salvar(this->fileName);

				if(nodoAbuelo.tipo == NODO_RAIZ)
				{
					//Recargo la raiz
					this->raiz.Limpiar();

					ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

					Puntero punteroRaiz;
					punteroRaiz.numBloque = BLOQUE_RAIZ;
					punteroRaiz.numNodo = NUM_NODO_RAIZ;

					this->raiz.Obtener(this->fileName, punteroRaiz);
				}
			}
		}
		else
		{
			NodoBSharpStringLong nodoHermanoDerecho;
			nodoHermanoDerecho.Obtener(this->fileName, nodoAbuelo.punteros[i+1]);

			if(nodoHermanoDerecho.CalcularTamanio(nodoHermanoDerecho) - 8 - nodoHermanoDerecho.claves.front().length() > (this->cabecera.EspacioMaximoAOcupar / 2))
			{
				pudeRedistribuir = true;

				//Busco la clave del abuelo que es mayor a la ultima del nodo padre
				//Lo encuentra seguro
				int i = 0;
				bool termino = false;
				while(!termino && i < nodoAbuelo.claves.size())
				{
					if(nodoAbuelo.claves[i].compare(nodoPadre.claves.back()) < 0)
						i++;
					else
						termino = true;
				}

				string claveParaElPadre;
				claveParaElPadre.assign(nodoAbuelo.claves[i]);

				nodoPadre.claves.push_back(claveParaElPadre);
				nodoPadre.punteros.push_back(nodoHermanoDerecho.punteros.front());
				nodoPadre.cantClavesUsadas++;

				nodoAbuelo.claves[i] = nodoHermanoDerecho.claves.front();

				nodoHermanoDerecho.claves.erase(nodoHermanoDerecho.claves.begin());
				nodoHermanoDerecho.punteros.erase(nodoHermanoDerecho.punteros.begin());
				nodoHermanoDerecho.cantClavesUsadas--;

				nodoPadre.Salvar(this->fileName);
				nodoHermanoDerecho.Salvar(this->fileName);
				nodoAbuelo.Salvar(this->fileName);

				if(nodoAbuelo.tipo == NODO_RAIZ)
				{
					//Recargo la raiz
					this->raiz.Limpiar();

					ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

					Puntero punteroRaiz;
					punteroRaiz.numBloque = BLOQUE_RAIZ;
					punteroRaiz.numNodo = NUM_NODO_RAIZ;

					this->raiz.Obtener(this->fileName, punteroRaiz);
				}
			}
			else
			{
				NodoBSharpStringLong nodoHermanoIzquierdo;
				nodoHermanoIzquierdo.Obtener(this->fileName, nodoAbuelo.punteros[i-1]);

				if(nodoHermanoIzquierdo.CalcularTamanio(nodoHermanoIzquierdo) - 8 - nodoHermanoIzquierdo.claves.back().length() > (this->cabecera.EspacioMaximoAOcupar / 2))
				{
					pudeRedistribuir = true;

					//Busco la clave del abuelo que es mayor a la ultima del nodo padre
					//Lo encuentra seguro
					int i = nodoAbuelo.claves.size() - 1;
					bool termino = false;
					while(!termino && i >= 0)
					{
						if(nodoAbuelo.claves[i].compare(nodoPadre.claves.front()) > 0)
							i--;
						else
							termino = true;
					}

					string claveParaElPadre;
					claveParaElPadre.assign(nodoAbuelo.claves[i]);

					nodoPadre.claves.insert(nodoPadre.claves.begin(), claveParaElPadre);
					nodoPadre.punteros.insert(nodoPadre.punteros.begin(), nodoHermanoIzquierdo.punteros.back());
					nodoPadre.cantClavesUsadas++;

					nodoAbuelo.claves[i] = nodoHermanoIzquierdo.claves.back();

					nodoHermanoIzquierdo.claves.erase(nodoHermanoIzquierdo.claves.end());
					nodoHermanoIzquierdo.punteros.erase(nodoHermanoIzquierdo.punteros.end());
					nodoHermanoIzquierdo.cantClavesUsadas--;

					nodoPadre.Salvar(this->fileName);
					nodoHermanoIzquierdo.Salvar(this->fileName);
					nodoAbuelo.Salvar(this->fileName);

					if(nodoAbuelo.tipo == NODO_RAIZ)
					{
						//Recargo la raiz
						this->raiz.Limpiar();

						ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

						Puntero punteroRaiz;
						punteroRaiz.numBloque = BLOQUE_RAIZ;
						punteroRaiz.numNodo = NUM_NODO_RAIZ;

						this->raiz.Obtener(this->fileName, punteroRaiz);
					}
				}
			}
		}

		if(!pudeRedistribuir)
		{
			if(nodoAbuelo.tipo == NODO_RAIZ)
			{
				if(nodoAbuelo.cantClavesUsadas == 1)
				{
					//Si es el primero
					if(i == 0)
					{
						NodoBSharpStringLong nodoHermanoDerecho;
						nodoHermanoDerecho.Obtener(this->fileName, nodoAbuelo.punteros[1]);

						nodoPadre.claves.push_back(nodoAbuelo.claves[0]);
						nodoPadre.cantClavesUsadas++;

						for(int j = 0; j < nodoHermanoDerecho.claves.size(); j++)
						{
							nodoPadre.claves.push_back(nodoHermanoDerecho.claves[j]);
							nodoPadre.cantClavesUsadas++;
						}

						for(int k = 0; k < nodoHermanoDerecho.punteros.size(); k++)
						{
							nodoPadre.punteros.push_back(nodoHermanoDerecho.punteros[k]);
						}

						//El nodoPadre pasa a ser la raiz
						nodoPadre.numBloque = BLOQUE_RAIZ;
						nodoPadre.numNodo = NUM_NODO_RAIZ;

						nodoPadre.Salvar(this->fileName);
					}
					else
					{
						NodoBSharpStringLong nodoHermanoIzquierdo;
						nodoHermanoIzquierdo.Obtener(this->fileName, nodoAbuelo.punteros[0]);

						nodoHermanoIzquierdo.claves.push_back(nodoAbuelo.claves[0]);
						nodoHermanoIzquierdo.cantClavesUsadas++;

						for(int j = 0; j < nodoPadre.claves.size(); j++)
						{
							nodoHermanoIzquierdo.claves.push_back(nodoPadre.claves[j]);
							nodoHermanoIzquierdo.cantClavesUsadas++;
						}

						for(int k = 0; k < nodoPadre.punteros.size(); k++)
						{
							nodoHermanoIzquierdo.punteros.push_back(nodoPadre.punteros[k]);
						}

						//El hermano izquierdo pasa a ser la raiz
						nodoHermanoIzquierdo.numBloque = BLOQUE_RAIZ;
						nodoHermanoIzquierdo.numNodo = NUM_NODO_RAIZ;

						nodoHermanoIzquierdo.Salvar(this->fileName);
					}
				}
				else
				{
					//Si es el mas a la derecha de los hijos
					if (i == nodoAbuelo.punteros.size() - 1)
					{
						NodoBSharpStringLong nodoHermanoIzquierdo;
						nodoHermanoIzquierdo.Obtener(this->fileName, nodoAbuelo.punteros[i-1]);

						//Lo encuentra seguro
						int i = 0;
						bool termino = false;
						while(!termino && i < nodoAbuelo.claves.size())
						{
							if(nodoAbuelo.claves[i].compare(nodoHermanoIzquierdo.claves.back()) < 0)
								i++;
							else
								termino = true;
						}

						string claveModificarAbuelo = nodoAbuelo.claves[i];

						nodoHermanoIzquierdo.claves.push_back(nodoAbuelo.claves[i]);
						nodoHermanoIzquierdo.cantClavesUsadas++;

						for(int j = 0; j < nodoPadre.claves.size(); j++)
						{
							nodoHermanoIzquierdo.claves.push_back(nodoPadre.claves[j]);
							nodoHermanoIzquierdo.cantClavesUsadas++;
						}

						for(int k = 0; k < nodoPadre.punteros.size(); k++)
						{
							nodoHermanoIzquierdo.punteros.push_back(nodoPadre.punteros[k]);
						}

						//Elimino de la raiz (nodoAbuelo) la clave y el puntero al nodoPadre
						//Saco directo los ultimos ya que el nodoPAdre era el ultimo de los hijos
						nodoAbuelo.claves.pop_back();
						nodoAbuelo.punteros.pop_back();
						nodoAbuelo.cantClavesUsadas--;

						nodoHermanoIzquierdo.Salvar(this->fileName);
						nodoAbuelo.Salvar(this->fileName);
					}
					else
					{
						NodoBSharpStringLong nodoHermanoDerecho;
						nodoHermanoDerecho.Obtener(this->fileName, nodoAbuelo.punteros[i+1]);

						//Lo encuentra seguro
						int i = 0;
						bool termino = false;
						while(!termino && i < nodoAbuelo.claves.size())
						{
							if(nodoAbuelo.claves[i].compare(nodoPadre.claves.back()) < 0)
								i++;
							else
								termino = true;
						}

						string claveModificarAbuelo = nodoAbuelo.claves[i];

						nodoPadre.claves.push_back(nodoAbuelo.claves[i]);
						nodoPadre.cantClavesUsadas++;

						for(int j = 0; j < nodoHermanoDerecho.claves.size(); j++)
						{
							nodoPadre.claves.push_back(nodoHermanoDerecho.claves[j]);
							nodoPadre.cantClavesUsadas++;
						}

						for(int k = 0; k < nodoHermanoDerecho.punteros.size(); k++)
						{
							nodoPadre.punteros.push_back(nodoHermanoDerecho.punteros[k]);
						}

						//Elimino de la raiz (nodoAbuelo) la clave y el puntero al nodoPadre
						//Saco directo los ultimos ya que el nodoPAdre era el ultimo de los hijos
						nodoAbuelo.claves.erase(nodoAbuelo.claves.begin() + i);
						nodoAbuelo.punteros.erase(nodoAbuelo.punteros.begin() + i + 1);
						nodoAbuelo.cantClavesUsadas--;

						nodoPadre.Salvar(this->fileName);
						nodoAbuelo.Salvar(this->fileName);
					}
				}

				//Recargo la raiz
				this->raiz.Limpiar();

				ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

				Puntero punteroRaiz;
				punteroRaiz.numBloque = BLOQUE_RAIZ;
				punteroRaiz.numNodo = NUM_NODO_RAIZ;

				this->raiz.Obtener(this->fileName, punteroRaiz);
			}
			else
			{
				//Si es el mas a la derecha de los hijos
				if (i == nodoAbuelo.punteros.size() - 1)
				{
					NodoBSharpStringLong nodoHermanoIzquierdo;
					nodoHermanoIzquierdo.Obtener(this->fileName, nodoAbuelo.punteros[i-1]);

					//Lo encuentra seguro
					int i = 0;
					bool termino = false;
					while(!termino && i < nodoAbuelo.claves.size())
					{
						if(nodoAbuelo.claves[i].compare(nodoHermanoIzquierdo.claves.back()) < 0)
							i++;
						else
							termino = true;
					}

					string claveModificarAbuelo = nodoAbuelo.claves[i];

					nodoHermanoIzquierdo.claves.push_back(nodoAbuelo.claves[i]);
					nodoHermanoIzquierdo.cantClavesUsadas++;

					for(int j = 0; j < nodoPadre.claves.size(); j++)
					{
						nodoHermanoIzquierdo.claves.push_back(nodoPadre.claves[j]);
						nodoHermanoIzquierdo.cantClavesUsadas++;
					}

					for(int k = 0; k < nodoPadre.punteros.size(); k++)
					{
						nodoHermanoIzquierdo.punteros.push_back(nodoPadre.punteros[k]);
					}

					nodoHermanoIzquierdo.Salvar(this->fileName);
					this->Despromover(claveModificarAbuelo, camino);
				}
				else
				{
					NodoBSharpStringLong nodoHermanoDerecho;
					nodoHermanoDerecho.Obtener(this->fileName, nodoAbuelo.punteros[i+1]);

					//Lo encuentra seguro
					int i = 0;
					bool termino = false;
					while(!termino && i < nodoAbuelo.claves.size())
					{
						if(nodoAbuelo.claves[i].compare(nodoPadre.claves.back()) < 0)
							i++;
						else
							termino = true;
					}

					string claveModificarAbuelo = nodoAbuelo.claves[i];

					nodoPadre.claves.push_back(nodoAbuelo.claves[i]);
					nodoPadre.cantClavesUsadas++;

					for(int j = 0; j < nodoHermanoDerecho.claves.size(); j++)
					{
						nodoPadre.claves.push_back(nodoHermanoDerecho.claves[j]);
						nodoPadre.cantClavesUsadas++;
					}

					for(int k = 0; k < nodoHermanoDerecho.punteros.size(); k++)
					{
						nodoPadre.punteros.push_back(nodoHermanoDerecho.punteros[k]);
					}

					nodoPadre.Salvar(this->fileName);
					this->Despromover(claveModificarAbuelo, camino);
				}
			}
		}
	}
}

void ArbolBSharpFrontCoding::Promover(vector<Puntero> camino, Puntero puntHijoNuevo, string clave)
{
	Puntero puntPadre = camino[camino.size() - 1];
	camino.erase(camino.end());

	NodoBSharpStringLong nodoPadre;
	nodoPadre.Obtener(this->fileName, puntPadre);

	// Busco lugar para insertar
	int pos = 0;
	while( (pos < nodoPadre.claves.size()) && (nodoPadre.claves.at(pos).compare(clave) < 0) )
		pos++;

	//Verifico si hay que hacer SPLIT o no
	if(nodoPadre.CalcularTamanio(nodoPadre) + 200 < this->cabecera.EspacioMaximoAOcupar)
	{
		//Si hay que agregarla al final
		if(pos >= nodoPadre.claves.size())
		{
			nodoPadre.claves.push_back(clave);
			nodoPadre.punteros.push_back(puntHijoNuevo);
		}
		else
		{
			vector<string>::iterator itClave;
			vector<Puntero>::iterator itPuntero;

			itClave = nodoPadre.claves.begin();
			itPuntero = nodoPadre.punteros.begin();

			nodoPadre.claves.insert(itClave + pos, clave);
			nodoPadre.punteros.insert(itPuntero + pos + 1, puntHijoNuevo);
		}

		nodoPadre.cantClavesUsadas++;
		nodoPadre.Salvar(this->fileName);

		//Si la raiz fue la ultima modificacion, entonces la cargo de vuelta
		if(nodoPadre.tipo == NODO_RAIZ)
		{
			this->raiz.Limpiar();

			ManejadorAccesoDatos manejadorDatos= ManejadorAccesoDatos(this->fileName, ABRIR);

			Puntero punteroRaiz;
			punteroRaiz.numBloque = BLOQUE_RAIZ;
			punteroRaiz.numNodo = NUM_NODO_RAIZ;

			this->raiz.Obtener(this->fileName, punteroRaiz);
		}
	}
	else
	{
		//SPLIT!!

		//Si hay que agregarla al final
		if(pos >= nodoPadre.claves.size())
		{
			nodoPadre.claves.push_back(clave);
			nodoPadre.punteros.push_back(puntHijoNuevo);
		}
		else
		{
			vector<string>::iterator itClave;
			vector<Puntero>::iterator itPuntero;

			itClave = nodoPadre.claves.begin();
			itPuntero = nodoPadre.punteros.begin();

			nodoPadre.claves.insert(itClave + pos, clave);
			nodoPadre.punteros.insert(itPuntero + pos + 1, puntHijoNuevo);
		}

		// Verifico si el split es sobre la raiz o un nodo indice
		if(nodoPadre.tipo == NODO_RAIZ)
		{
			NodoBSharpStringLong hijoIzq(NODO_INDICE);
			NodoBSharpStringLong hijoDer(NODO_INDICE);

			hijoIzq.numBloque = this->cabecera.UltimoBloque + 1;
			hijoIzq.numNodo = this->cabecera.UltimoNodo + 1;

			this->cabecera.UltimoBloque++;
			this->cabecera.UltimoNodo++;
			this->cabecera.CantNodosIndice++;

			hijoDer.numBloque = this->cabecera.UltimoBloque + 1;
			hijoDer.numNodo = this->cabecera.UltimoNodo + 1;

			this->cabecera.UltimoBloque++;
			this->cabecera.UltimoNodo++;
			this->cabecera.CantNodosIndice++;

			Puntero punteroIzquierdo;
			Puntero punteroDerecho;

			punteroIzquierdo.numBloque = hijoIzq.numBloque;
			punteroIzquierdo.numNodo = hijoIzq.numNodo;

			punteroDerecho.numBloque = hijoDer.numBloque;
			punteroDerecho.numNodo = hijoDer.numNodo;

			long tamanioNodoPadre = (nodoPadre.CalcularTamanio(nodoPadre) / 2);

			while((hijoIzq.CalcularTamanio(hijoIzq) + 16 + nodoPadre.claves[0].length()) < tamanioNodoPadre)
			{
				hijoIzq.claves.push_back(nodoPadre.claves.at(0));
				nodoPadre.claves.erase(nodoPadre.claves.begin());

				hijoIzq.punteros.push_back(nodoPadre.punteros.at(0));
				nodoPadre.punteros.erase(nodoPadre.punteros.begin());

				hijoIzq.cantClavesUsadas++;
			}
			hijoIzq.punteros.push_back(nodoPadre.punteros.at(0));
			nodoPadre.punteros.erase(nodoPadre.punteros.begin());

			string claveArriba = nodoPadre.claves.at(0);
			nodoPadre.claves.erase(nodoPadre.claves.begin());

			while(nodoPadre.claves.size() > 0)
			{
				hijoDer.claves.push_back(nodoPadre.claves.at(0));
				nodoPadre.claves.erase(nodoPadre.claves.begin());

				hijoDer.punteros.push_back(nodoPadre.punteros.at(0));
				nodoPadre.punteros.erase(nodoPadre.punteros.begin());

				hijoDer.cantClavesUsadas++;
			}
			hijoDer.punteros.push_back(nodoPadre.punteros.at(0));
			nodoPadre.punteros.erase(nodoPadre.punteros.begin());

			hijoIzq.Salvar(this->fileName);
			hijoDer.Salvar(this->fileName);

			//Actualizo la raiz
			this->raiz.cantClavesUsadas = 1;
			this->raiz.cantRegistrosUsados = 0;
			this->raiz.claves.clear();
			this->raiz.punteros.clear();
			this->raiz.registros.clear();

			this->raiz.claves.push_back(claveArriba);

			this->raiz.punteros.push_back(punteroIzquierdo);
			this->raiz.punteros.push_back(punteroDerecho);

			this->raiz.Salvar(this->fileName);
		}
		else
		{
			//Hago Split del nodo indice (el izquierda queda en el mismo bloque, se crea su hermano derecho)
			NodoBSharpStringLong nodoDer(NODO_INDICE);
			NodoBSharpStringLong nodoIzq(NODO_INDICE);

			nodoIzq.numBloque = nodoPadre.numBloque;
			nodoIzq.numNodo = nodoPadre.numNodo;

			nodoDer.numBloque = this->cabecera.UltimoBloque + 1;
			nodoDer.numNodo = this->cabecera.UltimoNodo + 1;

			Puntero punteroDerecho;

			punteroDerecho.numBloque = nodoDer.numBloque;
			punteroDerecho.numNodo = nodoDer.numNodo;

			this->cabecera.UltimoBloque++;
			this->cabecera.UltimoNodo++;
			this->cabecera.CantNodosIndice++;

			long tamanioNodoPadre = (nodoPadre.CalcularTamanio(nodoPadre) / 2);

			while((nodoIzq.CalcularTamanio(nodoIzq) + 16 + nodoPadre.claves[0].length()) < tamanioNodoPadre)
			{
				nodoIzq.claves.push_back(nodoPadre.claves.at(0));
				nodoPadre.claves.erase(nodoPadre.claves.begin());

				nodoIzq.punteros.push_back(nodoPadre.punteros.at(0));
				nodoPadre.punteros.erase(nodoPadre.punteros.begin());

				nodoIzq.cantClavesUsadas++;
			}
			nodoIzq.punteros.push_back(nodoPadre.punteros.at(0));
			nodoPadre.punteros.erase(nodoPadre.punteros.begin());

			string claveAPromover = nodoPadre.claves.at(0);
			nodoPadre.claves.erase(nodoPadre.claves.begin());

			while(nodoPadre.claves.size() > 0)
			{
				nodoDer.claves.push_back(nodoPadre.claves.at(0));
				nodoPadre.claves.erase(nodoPadre.claves.begin());

				nodoDer.punteros.push_back(nodoPadre.punteros.at(0));
				nodoPadre.punteros.erase(nodoPadre.punteros.begin());

				nodoDer.cantClavesUsadas++;
			}
			nodoDer.punteros.push_back(nodoPadre.punteros.at(0));
			nodoPadre.punteros.erase(nodoPadre.punteros.begin());

			nodoIzq.Salvar(this->fileName);
			nodoDer.Salvar(this->fileName);

			this->Promover(camino, punteroDerecho, claveAPromover);
		}
	}
}

void ArbolBSharpFrontCoding::Imprimir(Puntero puntero)
{
	NodoBSharpStringLong nodo;

	nodo.Obtener(this->fileName, puntero);

	if(nodo.tipo == NODO_HOJA)
	{
	  cout << "{" << nodo.numNodo << "} ";
		cout << "<" << nodo.anterior.numNodo << "> ";
		for(int i = 0; i < nodo.registros.size(); i++)
		{
			cout << "[" << nodo.registros[i].clave.substr(0, nodo.registros[i].clave.find_first_of("*")) << "] ";
		}
		cout << "<" << nodo.siguiente.numNodo << ">" << endl;
	}
	else if(nodo.tipo == NODO_INDICE)
	{
	  cout << "{" << nodo.numNodo << "} ";
		for(int i = 0; i < nodo.claves.size(); i++)
		{
			cout << "(" << nodo.punteros[i].numNodo << ") ";
			cout << "[" << nodo.claves[i].substr(0, nodo.claves[i].find_first_of("*")) << "] ";
		}
		cout << "(" << nodo.punteros[nodo.punteros.size() - 1].numNodo << ") " << endl;

		for(int j = 0; j < nodo.punteros.size(); j++)
		{
			this->Imprimir(nodo.punteros.at(j));
		}
	}
	else
	{
		if(nodo.cantRegistrosUsados > 0)
		{
		  cout << "{" << nodo.numNodo << "} ";
			cout << "<" << nodo.anterior.numNodo << "> ";
			for(int i = 0; i < nodo.registros.size(); i++)
			{
				cout << "[" << nodo.registros[i].clave.substr(0, nodo.registros[i].clave.find_first_of("*")) << "] ";
			}
			cout << "<" << nodo.siguiente.numNodo << ">" << endl;
		}
		else if(nodo.cantClavesUsadas > 0)
		{
		  cout << "{" << nodo.numNodo << "} ";
			for(int i = 0; i < nodo.claves.size(); i++)
			{
				cout << "(" << nodo.punteros[i].numNodo << ") ";
				cout << "[" << nodo.claves[i].substr(0, nodo.claves[i].find_first_of("*")) << "] ";
			}
			cout << "(" << nodo.punteros.at(nodo.punteros.size() - 1).numNodo << ") " << endl;

			for(int j = 0; j < nodo.punteros.size(); j++)
			{
				this->Imprimir(nodo.punteros[j]);
			}
		}
		else
		{
		  cout << "El arbol esta vacio" << endl;
		}
	}
}

vector<string> ArbolBSharpFrontCoding::RecorrerOrdenado()
{
	vector<string> array;
	ManejadorAccesoDatos manejadorDatos = ManejadorAccesoDatos(this->fileName, ABRIR);

	char* bloque = manejadorDatos.leerBloque(BLOQUE_RAIZ);

	Puntero punteroRaiz;
	punteroRaiz.numBloque = BLOQUE_RAIZ;
	punteroRaiz.numNodo = NUM_NODO_RAIZ;

	NodoBSharpStringLong nodo;
	nodo.Obtener(this->fileName, punteroRaiz);

	//Verifico si la raiz es nodo hoja
	if(nodo.cantRegistrosUsados > 0)
	{
		for(int i = 0; i < nodo.registros.size(); i++)
		{
			array.push_back(nodo.registros[i].clave.substr(0, nodo.registros[i].clave.find_first_of("*")));
		}
	}
	else
	{
	  if(nodo.tipo == NODO_RAIZ && nodo.cantClavesUsadas > 0)
	  {
	    Puntero puntero;

		while(nodo.tipo != NODO_HOJA)
		{
			puntero = nodo.punteros.at(0);
			nodo.Limpiar();
			nodo.Obtener(this->fileName, puntero);
		}

		while(nodo.siguiente.numNodo != -1)
		{
			for(int i = 0; i < nodo.registros.size(); i++)
			{
				array.push_back(nodo.registros[i].clave.substr(0, nodo.registros[i].clave.find_first_of("*")));
			}

			puntero = nodo.siguiente;
			nodo.Limpiar();
			nodo.Obtener(this->fileName, puntero);
		}

		for(int i = 0; i < nodo.registros.size(); i++)
		{
			array.push_back(nodo.registros[i].clave.substr(0, nodo.registros[i].clave.find_first_of("*")));
		}
		}
	}

	free(bloque);

	return array;
}

void ArbolBSharpFrontCoding::GuardarCabecera(){
	ManejadorAccesoDatos manejadorDatos = ManejadorAccesoDatos(this->fileName, ABRIR);

	char* bloque = manejadorDatos.inicillizarBloque(manejadorDatos.getTamanioBloques());
	char* bloqueIterador = bloque;

	memcpy(bloqueIterador, &(this->cabecera.CantNodosIndice), sizeof(this->cabecera.CantNodosIndice));
	bloqueIterador+=sizeof(this->cabecera.CantNodosIndice);
	memcpy(bloqueIterador, &(this->cabecera.CantNodosHojas), sizeof(this->cabecera.CantNodosHojas));
	bloqueIterador+=sizeof(this->cabecera.CantNodosHojas);
	memcpy(bloqueIterador, &(this->cabecera.UltimoNodo), sizeof(this->cabecera.UltimoNodo));
	bloqueIterador+=sizeof(this->cabecera.UltimoNodo);
	memcpy(bloqueIterador, &(this->cabecera.CantNodosPorBloque), sizeof(this->cabecera.CantNodosPorBloque));
	bloqueIterador+=sizeof(this->cabecera.CantNodosPorBloque);
	memcpy(bloqueIterador, &(this->cabecera.UltimoBloque), sizeof(this->cabecera.UltimoBloque));
	bloqueIterador+=sizeof(this->cabecera.UltimoBloque);
	memcpy(bloqueIterador, &(this->cabecera.EspacioMaximoAOcupar), sizeof(this->cabecera.EspacioMaximoAOcupar));
	bloqueIterador+=sizeof(this->cabecera.EspacioMaximoAOcupar);

	manejadorDatos.escribir(bloque, BLOQUE_CABECERA);

	free(bloque);
}

void ArbolBSharpFrontCoding::RecuperarCabecera(){
	ManejadorAccesoDatos manejadorDatos = ManejadorAccesoDatos(this->fileName, ABRIR);

	char* bloque = manejadorDatos.leerBloque(BLOQUE_CABECERA);
	char* bloqueIterador = bloque;

	memcpy(&(this->cabecera.CantNodosIndice), bloqueIterador, sizeof(this->cabecera.CantNodosIndice));
	bloqueIterador+=sizeof(this->cabecera.CantNodosIndice);
	memcpy(&(this->cabecera.CantNodosHojas), bloqueIterador, sizeof(this->cabecera.CantNodosHojas));
	bloqueIterador+=sizeof(this->cabecera.CantNodosHojas);
	memcpy(&(this->cabecera.UltimoNodo), bloqueIterador, sizeof(this->cabecera.UltimoNodo));
	bloqueIterador+=sizeof(this->cabecera.UltimoNodo);
	memcpy(&(this->cabecera.CantNodosPorBloque), bloqueIterador, sizeof(this->cabecera.CantNodosPorBloque));
	bloqueIterador+=sizeof(this->cabecera.CantNodosPorBloque);
	memcpy(&(this->cabecera.UltimoBloque), bloqueIterador, sizeof(this->cabecera.UltimoBloque));
	bloqueIterador+=sizeof(this->cabecera.UltimoBloque);
	memcpy(&(this->cabecera.EspacioMaximoAOcupar), bloqueIterador, sizeof(this->cabecera.EspacioMaximoAOcupar));
	bloqueIterador+=sizeof(this->cabecera.EspacioMaximoAOcupar);

	free(bloque);
}

ArbolBSharpFrontCoding::~ArbolBSharpFrontCoding() {
}



